package top.minuy.algorithm.sort.insertion;
/**
 * @author Minuy
 * @time 11:48
 * @date 2021/8/21
 */
public class InsertionSort {
    private InsertionSort() {
    }

    /***
     * 优化算法，减少了交换数据的步骤，有提升，找到位置后插入
     * @param arr 待排序数组
     * @param <E> 实现Comparable<E>
     */
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        // 同样的遍历全数组
        for (int i = 0; i < arr.length; i++) {

            // 暂存当前处理对象
            E temp = arr[i];

            // 从前面去寻找当前处理对象的位置
            for (int j = i; j > 0; j--) {  // 保证数组边界
                if (temp.compareTo(arr[j - 1]) < 0) {  // 如果前面的比当前处理对象大
                    arr[j] = arr[j - 1];  // 复制前面的到当前遍历位置来
                } else {  // 否则遇上小的了，即当前的j就是其位置了
                    arr[j] = temp;  // 放置当前处理对象
                    break;  // 退出，交给外层循环接着处理
                }
            }
        }
    }

    public static <E extends Comparable<E>> void sort(E[] arr, boolean isInverted) {
        if(isInverted){
            invertedSort(arr);
        }else {
            normalSort(arr);
        }
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        normalSort(arr);
    }

    public static <E extends Comparable<E>> void invertedSort(E[] arr) {
        for (int i=arr.length-1;i>=0;i--){
            E temp = arr[i];
            for (int j=i;j+1<arr.length;j++){
                if(temp.compareTo(arr[j+1]) > 0){
                    arr[j] = arr[j+1];
                }else {
                    arr[j] = temp;
                    break;
                }
            }
        }
    }

    /**
     * 初始版本，直接与前面的一个一个交换
     * @param arr 数组
     * @param <E> 泛型
     */
    public static <E extends Comparable<E>> void normalSort(E[] arr) {
        // 循环不变量：[0,i)的已处理，[i,n)
        // 依次遍历
        for (int i = 0; i < arr.length; i++) {
            // 插入，处理之前的
            // 循环不变量：j比j-1大？
            for (int j = i; j > 0; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0) { // 比它小，小于0，比它大，大于0
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[j];
        arr[j] = arr[i];
        arr[i] = t;
    }
}

